//给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。
//
// 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
//
// 请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。
//
//
//
// 示例 1:
//
//
//输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
//输出: [1,2],[1,4],[1,6]
//解释: 返回序列中的前 3 对数：
//    [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
//
//
// 示例 2:
//
//
//输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
//输出: [1,1],[1,1]
//解释: 返回序列中的前 2 对数：
//     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
//
//
// 示例 3:
//
//
//输入: nums1 = [1,2], nums2 = [3], k = 3
//输出: [1,3],[2,3]
//解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]
//
//
//
//
// 提示:
//
//
// 1 <= nums1.length, nums2.length <= 10⁴
// -10⁹ <= nums1[i], nums2[i] <= 10⁹
// nums1, nums2 均为升序排列
// 1 <= k <= 1000
//
//
//
//
//
// 注意：本题与主站 373 题相同：https://leetcode-cn.com/problems/find-k-pairs-with-smallest-
//sums/
//
// Related Topics 数组 堆（优先队列） 👍 80 👎 0


//? 暴力 实际上应该用堆的
function kSmallestPairs(nums1: number[], nums2: number[], k: number): number[][] {

    /**
     * @param {number[]} nums1
     * @param {number[]} nums2
     * @param {number} k
     * @return {number[][]}
     */
    let arr = []
    for(let i = 0 ; i<nums1.length;i++){
        for(let j = 0;j<nums2.length;j++){
            arr.push([nums1[i],nums2[j]])
        }
    }
    return arr.sort((a,b)=>(a[0]+a[1]) - (b[0]+b[1])).slice(0,k).map(a => [a[0],a[1]])


};

//? 贪心
function kSmallestPairs2(nums1: number[], nums2: number[], k: number): number[][] {
    /*
     * 我们可以创建一个长度为nums1.length的数组，来判断当前每个位置的值在另外数组中对应的指针位置；
     * 由于nums1.length的最大取值范围在1万，有可能超过k的1千,为了勤俭持家我们可以创建数组的时候取两者中的最小值去创建，节省空间；
     * 创建一个result数组，去存储我们的结果，当result.length < k时，我们每次从遍历所有位置找到其和对应指针的最小和；
     * 每一轮我们把和最小的两个元素push进数组中，同时该元素的指针往右移动一个位置；
     * 如果指针的位置已经到达最右边了，找下一个元素；
     * 如果没有下一个元素了，结束循环；
     * 当我们走到第一个指针为0的元素时候即可结束循环，因为当前索引的指针位置为0， 说明再往后的值也不可能有比当前值小的了。
     */
    let m = nums1.length, n = nums2.length;
    //? 记录每个位置的指针，索引从0开始
    let dp = new Array(Math.min(m, k)).fill(0);
    let result = [];

    while (result.length < k) {
        let minIndex = -1, minValue = Number.MAX_VALUE;
        for (let i = 0; i < dp.length; i++) {
            //? 兼容一下数量不够的情况
            if (dp[dp.length - 1] === n) return result;

            //? 走到尽头了，此路不通
            if (dp[i] === n) continue;

            let cur = nums1[i] + nums2[dp[i]];
            if (cur < minValue) {
                minIndex = i;
                minValue = cur;
            }

            //? 判断为空的时候不往后走
            if (dp[i] === 0) {
                break;
            }
        }

        //? 记录当前最小值，指针右移
        result.push([ nums1[minIndex], nums2[dp[minIndex]] ]);
        dp[minIndex]++;
    }

    return result;


};
//leetcode submit region end(Prohibit modification and deletion)
